//
// Created by Martin on 2022/5/8.
//
#include <vector>

using namespace std;

//------------------------------------------------
// 堆排序

// 大堆排序
class HeapSort {
public:
    static int root() {
        return 0;
    }

    static int lastNodeOfHeap() {
        return heapSize_ - 1;
    }

    static int leftChild(int i) {
        return i * 2 + 1;
    }

    static int rightChild(int i) {
        return i * 2 + 2;
    }

    // 以位置i的节点为子树根节点, 调整子树, 以维持堆特性
    static void maxHeapify(vector<int>& A, int i) {
        int l = leftChild(i);
        int r = rightChild(i);
        int largest;

        // 找根节点与左右孩子中, 值最大者位置largest
        if (l < heapSize_ && A[l] > A[i]) {
            largest = l;
        }
        else {
            largest = i;
        }

        if (r < heapSize_ && A[r] > A[largest]) {
            largest = r;
        }

        if (largest != i) {
            std::swap(A[largest], A[i]);
            maxHeapify(A, largest); // 以largest为新子树根节点, 调整子树
        }
    }

    static void buildMaxHeap(vector<int>& A) {
        heapSize_ = A.size();

        // 从最后一个非叶子节点开始向前扫描, 调整以满足堆特性
        for (int i = A.size() / 2 - 1; i >= 0; --i) {
            maxHeapify(A, i);
        }
    }

    static void heapSort(vector<int>& A) {
        // 建堆
        buildMaxHeap(A);

        // 交换堆末尾元素与根节点, i~A.end() 就是已排序序列
        for (int i = A.size() - 1; i >= 1; --i) {
            std::swap(A[0], A[i]);
            --heapSize_;
            maxHeapify(A, 0);
        }
    }

private:
    static int heapSize_;
};

int HeapSort::heapSize_ = 0;

//------------------------------------------------
// 测试

#include <random>
#include <algorithm>
#include <iostream>

void print_vector(vector<int>& vec) {
    cout << "{";
    for (int i = 0; i < vec.size(); ++i) {
        cout << vec[i];
        if (i < vec.size() - 1) {
            cout << ", ";
        }
    }
    cout << "}" << endl;
}

int main()
{
    // 生成 TestCase
    default_random_engine e;
    uniform_int_distribution<int> u(1, 100);
    const int kTestNum = 50;
    vector<int> vec;
    for (int i = 0; i < kTestNum; ++i) {
        vec.push_back(u(e));
    }

    // 打印 TestCase
    cout << "origin vector=";
    print_vector(vec);

    // 堆排序
    HeapSort::heapSort(vec);
    cout << "after heapsort, vector=";
    print_vector(vec);

    return 0;
}
